The Backup 2-Median Problem on Block Graphs

Yu-kun CHENG, Li-ying KANG, Hong YAN

应用数学学报(英文版) ›› 2014, Vol. 30 ›› Issue (2) : 309-320.

PDF(190 KB)
中国科学院数学与系统科学研究院期刊网
PDF(190 KB)
应用数学学报(英文版) ›› 2014, Vol. 30 ›› Issue (2) : 309-320. DOI: 10.1007/s10255-014-0294-y
ARTICLES

The Backup 2-Median Problem on Block Graphs

    Yu-kun CHENG1, Li-ying KANG2, Hong YAN3
作者信息 +

The Backup 2-Median Problem on Block Graphs

    Yu-kun CHENG1, Li-ying KANG2, Hong YAN3
Author information +
文章历史 +

摘要

The backup 2-median problem is a location problem to locate two facilities at vertices with the minimum expected cost where each facility may fail with a given probability. Once a facility fails, the other one takes full responsibility for the services. Here we assume that the facilities do not fail simultaneously. In this paper, we consider the backup 2-median problem on block graphs where any two edges in one block have the same length and the lengths of edges on different blocks may be different. By constructing a tree-shaped skeleton of a block graph, we devise an O(n logn+m)-time algorithm to solve this problem where n and m are the number of vertices and edges, respectively, in the given block graph.

Abstract

The backup 2-median problem is a location problem to locate two facilities at vertices with the minimum expected cost where each facility may fail with a given probability. Once a facility fails, the other one takes full responsibility for the services. Here we assume that the facilities do not fail simultaneously. In this paper, we consider the backup 2-median problem on block graphs where any two edges in one block have the same length and the lengths of edges on different blocks may be different. By constructing a tree-shaped skeleton of a block graph, we devise an O(n logn+m)-time algorithm to solve this problem where n and m are the number of vertices and edges, respectively, in the given block graph.

关键词

location theory / backup / median / block graph

Key words

location theory / backup / median / block graph

引用本文

EndNote

Ris (Procite)

Bibtex

导出引用
Yu-kun CHENG, Li-ying KANG, Hong YAN. The Backup 2-Median Problem on Block Graphs. 应用数学学报(英文版), 2014, 30(2): 309-320 https://doi.org/10.1007/s10255-014-0294-y
Yu-kun CHENG, Li-ying KANG, Hong YAN. The Backup 2-Median Problem on Block Graphs. Acta Mathematicae Applicatae Sinica(English Series), 2014, 30(2): 309-320 https://doi.org/10.1007/s10255-014-0294-y

参考文献

[1] Aho, A.O., Hopcropt, J.E., Ullman, J.D. The Design and Analysis of Computer Algorithms. Addison- Wesley, Reading, MA, 1974
[2] Benkoczi R. Cardinality constrained facility location problems in trees. Ph.D. Thesis, Simon Fraser University, 2004
[3] Benkoczi, R., Breton, D., Bhattacharya, B. Efficient computation of 2-medians in a tree network with positive/negative weights. Discrete Mathematics 306: 1505-1516 (2006)
[4] Bondy, J.A., Murty, U.S.R. Graph Theory. Springer, Reading, DOI: 10.1007/978-1-84628-970-5, 2007
[5] Burkard, R.E., Cela, E., Dollani, H. 2-median in trees with pos/neg weights. Discrete Appl. Math., 105: 51-71 (2000)
[6] Burkard, R.E., Fathali, J. A polynomial method for the pos/neg weighted 3-medians problem on a tree. Math. Meth. Oper. Res., 65: 229-238 (2007)
[7] Burkard, R.E., Fathali, J., Kakhki, H.T. The p-maxian problem on a tree. Oper. Res. Lett., 35: 331-335 (2007)
[8] Chen, M.L., Francis, R.L., Lowe, T.J. The 1-center problem: exploiting block structure. Trans. Sci. 22: 259-269 (1988)
[9] Burkard, R.E., Hatzl, J. Median problems with positive and negative weights on cycles and cacti. J. Comb. Optim., 20: 27-46 (2010)
[10] Burkard, R.E., Krarup, J. A linear algorithm for the pos/neg-weighted 1-median problem on a cactus. Computing, 60: 193-215 (1998)
[11] Cheng, Y.K., Kang, L.Y. The p-maxian problem on interval graphs. Discrete Appl. Math., 158: 1986-1993 (2010)
[12] Cheng, Y.K., Kang L.Y., Lu, C.H. The pos/neg-weighted 1-median problem on tree graphs with subtree- shaped customers. Theor. Comput. Sci., 411: 1038-1044 (2010)
[13] Hatzl, J. Median problems on wheels and cactus graphs. Computing, 80: 377-393 (2007)
[14] Hua, L. Applications of mathematical methods for wheat harvesting. Chinese Math., 2: 77-91 (1962)
[15] Goldman, A.J. Optimal center location in simple networks. Transp. Sci., 5: 212-221 (1971)
[16] Gavsih, B., Sridhar, S. Computing the 2-median on tree networks in O(n log n) time. Networks, 26: 305-317 (1995)
[17] Kang, L.Y., Cheng, Y.K. The p-maxian problem on block graphs. J. Comb. Optim., 20: 131-141 (2010)
[18] Kariv, O., Hakimi, S. An algorithmic approach to network location problems, part II: p-medians. SIAM J. Appl. Math., 27: 539-560 (1979)
[19] Snyder, L.V. Facility location under uncertainty: a review. IIE Trans, 38: 537-554 (2006)
[20] Snyder, L.V., Daskin, M.S. Reliability models for facility location: the expected failure cost case. Transp. Sci., 39: 400-416 (2005)
[21] Snyder, L.V., Daskin, M.S. Stochastic p-robust location problems. IIE Trans, 38: 971-985 (2006)
[22] Tamir, A. An O(pn2) algorithm for the p-median and related problems on tree graphs. Oper. Res. Lett., 19: 59-64 (1996)
[23] Wang, H.L., Wu, B.Y., Chao, K.M. The backup 2-center and backup 2-median problems on trees. Networks., 53: 39-49 (2009)
[24] Wu, B.Y., Chao, K.M. Spanning trees and optimization problems. Chapman and Hall/CRC Press, Boca Raton, Florida, 2004
[25] Zhang, X.Q., Kang, L.Y., Cheng, Y.K. The pos/neg-weighted median on block graphs with subgraph- shaped customers. Computing, 88: 97-110 (2010)

基金

Supported by the National Natural Science Foundation of China (No. 11301475, 11126202, 11171207), the Nature Science Foundation of Zhejiang Province (No. LQ12A01011) and partially supported by The Hong Kong CERG Research Fund PolyU 5515/10H.
PDF(190 KB)

83

Accesses

0

Citation

Detail
段落导航
相关文章

/

〈 〉